import java.util.Arrays;
import java.util.Scanner;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Gao zhao xu
 * Date: 2023-10-19
 * Time: 16:09
 */
public class test {
//第一题
    public static int[] findNext(String s1, String s2) {
        int i = 0;
        int k = -1;
        String P = s1 + s2;
        int m = P.length();					// m为模式P的长度
        int[] next = new int[m];				// 动态存储区开辟整数数组
        next[0] = -1;
//        while (i < m - 1) {					// 若写成 i < m 会越界
//            while (k >= 0 && P.charAt(k) != P.charAt(i))	// 采用 KMP 找最大首尾子串
//                k = next[k];				// k 递归地向前找
//            i++;
//            k++;
//            next[i] = k;
//        }
        while (i < m - 1){
            if (k == -1 || P.charAt(k) == P.charAt(i)) next[++i] = ++k;
            else k = next[k];
        }
        return next;
    }
//    public static boolean KMPStrMatching(String s1, String s2, int[] N) {
//        int i = 0;
//        int j = 0;
//        int s1Len = s1.length(); // 模式的长度
//        int s2Len = s2.length(); // 模式的长度
//        if (s1Len != s2Len) return false;
//        String s = s1 + s2;
//        int sLen = s.length(); // 目标的长度
//        if (sLen  < s2Len) return false;// 若目标比模式短，匹配无法成功
//
//        while (i < sLen && j < s2Len) { // 反复比较，进行匹配
//            if (j == -1 || s.charAt(i)== s2.charAt(j)){
//                i++;
//                j++;
//            }else j = N[j];	// 不相等，按照特征向量调整
//        }
//        if (j >= s2Len) return true; // 注意仔细算下标
//        else return false;
//    }
//   第二题
//    public static int findNext(String P1, String P2){
//        int i = 0;
//        int k = -1;
//        String P = P1 + P2;
//        int m = P.length();
//        int[] next = new int[m + 1];
//        next[0] = -1;
//        while (i < m ) {
//            while (k >= 0 && P.charAt(k) != P.charAt(i))
//                k = next[k];
//            i++;
//            k++;
//            next[i] = k;
//        }
//        return next[m];
//    }
//第三题
//    public static void del(String arr){
//        String[] s = arr.split("");
//        int j = -1;
//        for (int i = 0; i < s.length; i++){
//            if (s[i].equals("b") ){
//                continue;
//            }else if (s[i].equals("c")) {
//                if (j >= 0 && s[j].equals("a")){
//                    j--;
//                }else{
//                    s[++j] = "c";
//                }
//            }else {
//                s[++j] = s[i];
//            }
//        }
//        for (int i = 0; i <= j; i++){
//            System.out.print(s[i]);
//        }
//        System.out.println();
//    }

    public static void main(String[] args) {
        int[] a = findNext("abad", "");
        for (int x : a){
            System.out.print(x + " ");
        }
    }
}
